A data communications network can generally be defined as a collection of network nodes and access nodes interconnected through communication links. A network node is generally a high cost data processing system that provides certain functions within the network, such as routing of messages (generally in the form of data packets) between itself and neighboring nodes, selection and optimization of routes for messages to be transmitted within the network and furnishing directory services to locate resources. Comparatively, access nodes are low cost data processing systems, offering to attached users a high level of access services but providing a limited set of routing, path selection and directory services. The links between nodes may be permanent communications links such as conventional cable connections or links that are enabled only when needed, such as dial-up connections through public or private telephone systems.
The number of access nodes in a network is expected to be much greater than the number of network nodes. Collectively, the network nodes, the access nodes and the links between the nodes are referred to as network resources. The physical configuration and characteristics of the network resources are said to be the topology of the network.
Route management is the network layer protocol that guides packets to their correct destination. Two aspects have to be considered:
1. determining what the route for a given connection shall be; PA1 2. actually switching (routing) the packet within a node. This aspect is particularly critical in high speed packet switching networks since the switching element must be able to decide where to route an incoming packet in a very short portion of time. PA1 The source node (or the node providing calculation for the source node) must be able to decide where to route an incoming connection in a very short period of time (the computation must be rapid enough to compute an optimum path for each connection request); this is a major requirement. PA1 The switching time in the intermediate nodes must be minimized (minimum processing time). PA1 The network resources along the selected path must be optimized according to user criteria. PA1 Control messages must be limited as much as possible to avoid overloading the network. PA1 (1) a search request for a target Y is sent by "ENA" to its network node server "NNA" to locate station Y; PA1 (2) assuming "NNA" has no idea of the target Y resource's location, "NNA" initiates a broadcast search into the network; PA1 (3) the broadcast search from "NNA" is received by end node "ENB", the "owner" of user Y; PA1 (4) "ENB" builds a locate reply message and sends it back to its network node server, in our example "NND"; PA1 (5) "NND" then adds to the locate reply message the local topology information for "ENB" that is "ENB", link information between "ENB" and "NND", and link information between "ENB" and "NNC"; PA1 (6) the locate reply message is finally sent back to "ENA". PA1 defining in each access node a so-called Access Node Connection Table (ANCT) for storing therein a list including every remote AN for which there is at least one user connection with the considered access node, and identifying said connection; PA1 defining in the locate reply message format a field for the destination remote Access Node Topology DataBase (ANTDB) and inserting the remote ANTDB information therein prior to sending the reply message; PA1 monitoring the locate reply message reception within the considered local AN, and upon reception of the locate reply message, creating an entry for storing in the local AN the received remote ANTDB, unless the considered remote AN was already identified in the local AN; then, PA1 conventionally selecting the optimal path and setting the connection accordingly; and, PA1 updating the ANCT table to include predefined information relative to the new set-up path.
There are many methods to route a packet through a network. A first method can be called "dynamic node by node routing". With this method there is no route determined when the connection is set up. This is due to the fact that there is no connection. Each packet is sent into the network with its full destination address imbedded in the header. Each node knows the current network topology and loading and is able to decide where and on which path the packet should be directed. This process, even if it can be very fast is a software based technique. It is very difficult to see how it could be efficiently implemented in hardware. Packet rates of millions per second are not likely to be achieved by this method very soon.
This is the reason why, for high speed packet switching networks, another method named "source routing" is chosen preferably. In the source routing method the originating node is responsible for calculating the route the packet must take through the network. A routing field is appended to every packet sent and that field is used by the intermediate nodes to direct the packet towards its destination. The sending node must either know the network topology or it must use some method (such as broadcasting) to find the optimal route. But once the route is determined, intermediate switches do not need to refer to any system tables or parameters to make the routing decision. Depending on whether the network is "connection oriented" or "connectionless", two techniques are used. The first one, used in connectionless networks, consists in appending a routing vector to every packet sent and that vector is used by intermediate nodes to route the packet towards its destination. A drawback of this technique is that the routing vector requires some storage and so constitutes an overhead. This overhead may become unacceptable for a high speed real time network. This is the reason why another technique named "label swapping" is regarded by many as an appropriate technique for supporting source routing in high speed networks. The label swapping is a particular implementation of the source routing method for connection oriented networks. Each packet sent on the link has a header which includes an arbitrary number (called label) identifying which logical connection this packet belongs to. In such networks the call setup and the resource reservation process requires first that a connection be requested from a calling source to a target destination, then a route should be defined and finally reserved. The connection request is specified by the user via a set of parameters including origin and destination address and data flow characteristics. The route determination is realized by the source node using its local routing topology database. And finally the route reservation is sent out in a special message along the nodes specified during the route determination process. That message signals the intermediate nodes to set up their connection tables and to reserve their resources to provide the service level required by the connection request. The connection is then said to be set up.
It shall be noticed that a good source routing mechanism in large and high speed packet switching networks supporting connection oriented routing mode implies some requirements in terms of performance and resource consumption which can be summarized as follows:
Route determination and topology maintenance within a network typically involve a rather complex collection of algorithms that work more or less independently and yet support each other by exchanging services or information. The complexity is due to a number of reasons. First, it requires coordination between all the nodes rather than just a pair of nodes. Second, the routing algorithm must cope with link and node failures, requiring redirection of traffic and updates of the databases maintained by the system. Third, to achieve performance, it may need to modify its routes when some areas within the network become congested.
The subject invention focuses on the way to generate and maintain routing-related information even in case of link and node failures to all access nodes within a network, while minimizing processing time and software and hardware required.
Different methods including the so-called flooding mechanism and spanning tree mechanism are used to broadcast and maintain routing information within a network. Let's examine first the flooding mechanism, then the use of a spanning tree. Then we shall take a look at the way IBM Advance Peer-to-Peer Networking architecture (APPN) has solved the route determination issue in a network composed of network nodes and access nodes.
As shown in FIG. 1A the flooding method operates as follows. The origin node (e.g. node A) sends its information in the form of a packet to its neighbors (the nodes to which it is directly connected with a link). The neighbors relay it to their neighbors, and so on, until the packet reaches all nodes in the network. Two additional rules are also observed, which limit the number of packet transmissions. First, a node will not relay the packet back to the node from which the packet was obtained. Second, a node will transmit the packet to its neighbors at most once. This can be ensured by including in the packet the identification(ID) number of the origin node, a sequence number, which is incremented with each new packet issued by the origin node. By storing the highest sequence number received for each origin node, and by not relaying packets with sequence numbers that are less than or equal to the one stored, a node can avoid transmitting the same packet more than once on each of its incident links. With these rules, the links do not have to preserve the order of packet transmissions; the sequence numbers can be used to recognize the correct order.
FIG. 1-A illustrates that the total number of packet transmissions per packet broadcast lies between L and 2L, where L is the number of bi-directional links of the network. It also shows the sequence of packet transmissions to that end (see numbered arrows), with each packet transmission time being assumed to be over one unit. This method is not very efficient.
Another method is based on the use of a spanning tree. A spanning tree is a connected subgraph of the network that includes all nodes and has no cycles. Broadcasting on a spanning tree is more communication efficient than flooding. It requires a total of only N-1 packet transmissions per packet broadcast, where N is the number of nodes in the network. This is illustrated in FIG. 1B showing a network built of nodes and a spanning tree interconnecting these nodes. The spanning tree connects every node without any loop. The spanning tree is represented by dashed lines.
In addition to the bandwidth efficiency, the spanning tree can be optimized to fulfill a preferred criteria such as: select highest bandwidth links, lower cost links, lower transit delay links, etc.
The main drawback of this method is the need to maintain and update the spanning tree in the face of topological changes. Therefore there is a need to keep up-date databases.
The performance that we can expect from such a mechanism is directly related to the number of network resources, i.e. nodes and links. For large networks this can become unacceptable, because of the amount of network control traffic that it might generate (it's very unlikely that a customer would accept that the bandwidth on a trunk is not fully dedicated for user connections). Also the topology database could be dramatically large.
Therefore it appears necessary to avoid replicating the routing information in all nodes of the network. This approach applies particularly well to the case of a network composed of both network nodes and access nodes while minimizing average set-up process.
The IBM Advanced Peer to Peer Networking architecture introduces the concept of network nodes and access nodes (also called end nodes). Network nodes provide route selection services, directory services, intermediate routing and management services to end/access nodes. Access nodes are simpler nodes, which primarily serve end users located at the boundary of the network. An access node does not provide any network service to other nodes and does not support route selection nor intermediate routing functions. An access node must select an APPN network node and request this network node to be its network node server. The APPN access node will use the directory and routing facilities of the network node to locate resources within the network and to establish connections with them. An interesting thing in this approach is the way in which the network topology is handled. APPN systems have two kinds of topology databases; the local topology database and the network topology database. Every APPN end node maintains a local topology database. Every APPN network node maintains a network topology database. Local and network topology databases are used for route calculation. The local topology database contains information on the local node's properties and on all the links attached to the node. The network topology database contains information on all network nodes in the APPN network and the transmission links between them, including information of the transmission links local to that node. It does not include information on access nodes. The network topology database is fully replicated at each network node using a flooding mechanism.
The computation of a route between access nodes or between an access node and network node requires routing information about the access node(s) which is not contained in the network topology but obtained directly from the access node(s), during the resource discovery phase of connection setup. Using network topology, desired class of service specified in the connection setup and routing information from the access nodes, a route selection process is able to find the optimal path within the network.
The method is illustrated with reference to FIG. 2 showing a simplified network. Four network nodes (NNA, NNB, NNC, NND) are interconnected. Additionally, there are two end access nodes (ENA and ENB) each connected to two network nodes. Suppose user X (herein also designated as calling or source end-user) attached to end node "ENA" requests a connection to end user Y (also designated as target or destination end user), then:
Now ENA is able to request from its server network node "NNA" a route between ENA and ENB. It provides origin node name "ENA", destination node name "ENB" plus the local topology information for "ENA" and "ENB".
All the necessary information is now available to topology and routing services to compute the optimum route.
A drawback of this method is that the only way to use accurate topology information for a remote end node is to always request, at each connection setup, the directory services function to carry back the remote topology information prior to issuing the route request to topology and route services. This significantly increases the connection setup time.